package swordoffer.offer10;

/**
 * 递归方法，O（2^n），该解法会超出时间限制
 */
public class FibRecursion {
    int constant = 1000000007;
    public int fib(int n) {
        if(n < 2){
            return n;
        }
        int first = fib(n - 1) % constant;
        int second = fib(n - 2) % constant;
        return first + second;
    }
}
